package problemas;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

import busca.BuscaAEstrela;
import busca.BuscaLargura;
import busca.BuscaProfundidade;
import busca.BuscaProfundidadeIterativa;
import busca.Estado;
import busca.Heuristica;
import busca.No;

public class EstadoGramatica implements Estado,Heuristica{

	Vector<String> actualState;
	Gramatica1 gramatica1;
	Gramatica2 gramatica2;
	static Gramatica gramatica;

	public EstadoGramatica(Vector<String> atualState, Gramatica gramatica) {
		actualState = atualState;
		//this.gramatica1 = new Gramatica1();
		//this.gramatica2 = new Gramatica2();
		this.gramatica = gramatica;

	}

	public Vector<String> getActualState() {
		return actualState;
	}
	@Override
	public List<Estado> sucessores() {
		List<Estado> retorno = new LinkedList<Estado>();

		for (int i=0;i<actualState.size();i++) {
			ArrayList<Vector> array = this.gramatica.getRules().get(actualState.get(i).trim());
			if(array != null ){
				for(int j = 0; j < array.size();j++){
					Vector newState = array.get(j);
					Vector stadoAtual = getActualStateCopy();
					stadoAtual.remove(i);

					for(int h =0;h<newState.size();h++){
						stadoAtual.add(h+i, newState.get(h));
					}

					EstadoGramatica novo = new EstadoGramatica(stadoAtual,gramatica);
					retorno.add(novo);
				}
			}

		}

		return retorno;
	}

	public Vector<String> getActualStateCopy(){
		if(actualState != null){
			Vector<String> retorno = new Vector<String>();
			for(int i=0;i<actualState.size();i++){
				retorno.add(actualState.get(i));
			}
			return retorno;
		}
		return null;
	}

	public static EstadoGramatica getEstadoMeta() {
		return estadoMeta;
	}

	private final static EstadoGramatica estadoMeta = setEstadoMeta();
	private static EstadoGramatica setEstadoMeta() {
		Vector<String> vector = new Vector<String>();
		//string de entrada1
//		vector.add("(");
//		vector.add("expr");
//		vector.add(")");

		//		string de entrada2
//				vector.add("id");
//				vector.add("+");
//				vector.add("id");

		//		string de entrada3
//				vector.add("(");
//				vector.add("id");
//				vector.add("+");
//				vector.add("id");
//				vector.add(")");
//				vector.add("+");
//				vector.add("id");

		//		string de entrada4
//				vector.add("(");
//				vector.add("id");
//				vector.add("+");
//				vector.add("id");
//				vector.add(")");

		//		string de entrada5
//				vector.add("id");
//				vector.add("+");
//				vector.add("(");
//				vector.add("id");
//				vector.add("+");
//				vector.add("id");
//				vector.add(")");
				
				//		string de entrada5
				vector.add("(");
				vector.add("id");
				vector.add("+");
				vector.add("id");
				vector.add(")");
				vector.add("/");
				vector.add("id");

		//		vector.add("a");
		//		vector.add("a");
		//		vector.add("b");
		//		vector.add("b");
		EstadoGramatica e8 = new EstadoGramatica(vector,gramatica);
		return e8;
	}

	@Override
	public int h() {
		//return 1;
		return h1()+h2();
		//return h1();
	}

	//verifica a quantidade de simbolos iguais
	public int h1() {
		Vector<String> metaState = estadoMeta.getActualState();
		int soma = 0;
		for(int i =0;i<actualState.size();i++){
			for(int j=0;j<metaState.size();j++){
				if(actualState.get(i).equalsIgnoreCase(metaState.get(j))){
					soma++;
				}
			}

		}
		return 100-soma;
	}

	//posicoes iguais com simbolos iguais no estado atual como no estado meta
	public int h2() {
		Vector<String> metaState = estadoMeta.getActualState();
		int soma = 0;
		for(int i =0;i<actualState.size();i++){
			if(metaState.size() > i){
				if(actualState.get(i).equalsIgnoreCase(metaState.get(i))){
					soma++;
				}
			}
		}

		return 100-soma;
	}
	
	
	//maior sequencia comum entre os estados
	public int h3(){
		String x = statetoString(actualState)/*"(expr expr)"*/;
		String y = statetoString(estadoMeta.getActualState())/*"(id+id)+id"*/;
		int M = x.length();
		int N = y.length();

		StringBuilder retorno = new StringBuilder();

		// opt[i][j] = length of LCS of x[i..M] and y[j..N]
		int[][] opt = new int[M+1][N+1];

		// compute length of LCS and all subproblems via dynamic programming
		for (int i = M-1; i >= 0; i--) {
			for (int j = N-1; j >= 0; j--) {
				if (x.charAt(i) == y.charAt(j))
					opt[i][j] = opt[i+1][j+1] + 1;
				else 
					opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
			}
		}

		// recover LCS itself and print it to standard output
		int i = 0, j = 0;
		while(i < M && j < N) {
			if (x.charAt(i) == y.charAt(j)) {
				//System.out.print(x.charAt(i));
				retorno.append(x.charAt(i));
				i++;
				j++;
			}
			else if (opt[i+1][j] >= opt[i][j+1]) i++;
			else                                 j++;
		}
		//System.out.println();
		//System.out.println(retorno.toString());

		int tamMetaState = y.length();
		int tamResultado = retorno.toString().length();
		double res = tamMetaState/tamMetaState;
		
		return (100 - (int)res);
	}
	
	public int h4(){
		return 0;
	}
	
	public String statetoString(Vector<String> state){
		StringBuilder retorno = new StringBuilder();
		if(state !=null){
			for(int x=0;x<state.size();x++){
				retorno.append(state.get(x));
			}
		}
		return retorno.toString();
	}


	@Override
	public boolean isGoal() {
		if(actualState.size() == estadoMeta.actualState.size()){
			for(int i =0;i<actualState.size();i++){
				String actualStateI = actualState.get(i);
				String estadoMetaActualState = estadoMeta.actualState.get(i);
				if(!estadoMetaActualState.equalsIgnoreCase(actualStateI)){
					return false;
				}
			}
			return true;
		}
		return false;
	}

	@Override
	public int custo() {
		return 1;
	}

	public String toString() {
		StringBuffer r = new StringBuffer("\n");
		if(actualState != null){
			for (int i=0;i<actualState.size();i++) {
				if(i!=0){
					r.append(" ");
				}
				r.append(actualState.get(i));

			}
		}
		return r + "";    
	}


	public static void main(String[] args) {
		Vector<String> vetor = new Vector<String>();
		vetor.add("i");

		Gramatica1 gramatica1 = new Gramatica1();
		Gramatica2 gramatica2 = new Gramatica2();

		EstadoGramatica state  = new EstadoGramatica(vetor, gramatica1);

		System.out.println("Estado inicial:"+state);

		BuscaAEstrela buscaAEstrela = new BuscaAEstrela();
		No s1 = buscaAEstrela.busca(state);

		BuscaLargura buscaLargura = new BuscaLargura();
		No s2 = buscaLargura.busca(state);

		BuscaProfundidadeIterativa buscaProfundidadeIterativa = new BuscaProfundidadeIterativa();
		No s3 = buscaProfundidadeIterativa.busca(state);

		BuscaProfundidade buscaProfundidade = new BuscaProfundidade(25);
		No s4 = buscaProfundidade.busca(state);

		if (s1 != null) {
			//System.out.println("**** ALGORITMO A ESTRELA *****");
			//System.out.println("Solucao A estrela:" +s1.retornaCaminho());
			//System.out.println("Profundidade A estrela: "+s1.getProfundidade());
			//System.out.println("Tempo A estrela:"+ buscaAEstrela.getRunningTimeInSeconds()+"ms");
			//System.out.println("Nos Visitados:"+ buscaAEstrela.getNosVisitados()+"");
			//System.out.println("");
			System.out.println(buscaAEstrela.getRunningTimeInSeconds());
		}else{
			System.out.println("**** ALGORITMO A ESTRELA *****");
			System.out.println("Tempo Esgotado");
			System.out.println("");
		}
		if (s2 != null) {
			//			System.out.println("**** BUSCA LARGURA *****");
			//			System.out.println("Profundidade Busca Largura: "+s2.getProfundidade());
			//			System.out.println("Tempo Busca Largura:"+ buscaLargura.getRunningTimeInSeconds()+"ms");
			//			System.out.println("Nos Visitados:"+ buscaLargura.getNosVisitados());
			//			System.out.println("");
			System.out.println(buscaLargura.getRunningTimeInSeconds());
		}else{
			System.out.println("**** BUSCA LARGURA  *****");
			System.out.println("Tempo Esgotado");
			System.out.println("");
		}
		if (s3 != null) {
			//			System.out.println("**** BUSCA PROFUNDIDADE ITERATIVA *****");
			//			// System.out.println("Solucao Busca Profundidade Iterativa:" +s3.retornaCaminho());
			//			System.out.println("Profundidade Busca Profundidade Iterativa: "+s3.getProfundidade());
			//			System.out.println("Tempo  Busca Profundidade Iterativa:"+ buscaProfundidadeIterativa.getRunningTimeInSeconds()+"ms");
			//			System.out.println("Nos Visitados:"+ buscaProfundidadeIterativa.getNosVisitados());
			//			System.out.println("");
			System.out.println(buscaProfundidadeIterativa.getRunningTimeInSeconds());
		}else{
			System.out.println("**** BUSCA PROFUNDIDADE ITERATIVA *****");
			System.out.println("Tempo Esgotado");
			System.out.println("");
		}
		if (s4 != null) {
			//			System.out.println("**** BUSCA PROFUNDIDADE *****");
			//			//System.out.println("Solucao Busca Profundidade:" +s4.retornaCaminho());
			//			System.out.println("Profundidade Busca Profundidade: "+s4.getProfundidade());
			//			System.out.println("Tempo  Busca Profundidade:"+ buscaProfundidade.getRunningTimeInSeconds()+"ms");
			//			System.out.println("Nos Visitados:"+ buscaProfundidade.getNosVisitados());
			//			System.out.println("");
			System.out.println(buscaProfundidade.getRunningTimeInSeconds());
		}else{
			System.out.println("**** BUSCA PROFUNDIDADE *****");
			System.out.println("Tempo Esgotado");
			System.out.println("");
		}

	}





}
